﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class SumsInATriangle
    {
        public SumsInATriangle()
        {
            int testCase = Int32.Parse(Console.ReadLine());
            while (testCase-- > 0)
            {
                int rows = Int32.Parse(Console.ReadLine());
                int[,] triangle = new int[rows, rows];
                for (int i = 0; i < rows; i++)
                {
                    string[] consoleInput = Console.ReadLine().Split(' ');
                    for (int j = 0; j < i + 1; j++)
                    {
                        triangle[i, j] = Int32.Parse(consoleInput[j]);
                    }
                }
                for (int i = rows - 2; i >= 0; i--)
                {
                    int iplus1 = i + 1;
                    for (int j = 0; j < iplus1; j++)
                    {
                        triangle[i, j] = triangle[i, j] + Math.Max(triangle[iplus1, j], triangle[iplus1, j + 1]);
                    }
                }
                Console.WriteLine(triangle[0, 0]);
            }
        }
    }
}
